package com.zzy.algorithm.linkedList;

import com.zzy.algorithm.model.ListNode;

/**
 * LeetCode - 160 : 相交链表
 *
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 题解思路：
 * 方法一：哈希表
 *  利用set集合判断当前集合中是否存在过该节点
 * 方法二：遍历差值
 *  遍历出两个链表的差值，做到同时出发，再判断是否相交
 * 方法三：双指针（推荐）
 *  定义两个指针，初始位置分别指向链表头部，指针1从headA遍历到末尾后移动到HeadB头部，指针2从headB遍历到末尾后移动到HeadA头部
 */
public class Q11_IntersectLinkedList {

    public static void main(String[] args) {
        ListNode c3 = new ListNode(8,null);
        ListNode c2 = new ListNode(7,c3);
        ListNode c1 = new ListNode(6,c2);

        ListNode a2 = new ListNode(5,c1);
        ListNode a1 = new ListNode(4,a2);

        ListNode b3 = new ListNode(3,c1);
        ListNode b2 = new ListNode(2,b3);
        ListNode b1 = new ListNode(1,b2);
        Q11_IntersectLinkedList q11_intersectLinkedList = new Q11_IntersectLinkedList();
        ListNode solution = q11_intersectLinkedList.solution(a1, b1);
        System.out.println("solution = " + solution.val);

    }


    public ListNode solution(ListNode headA, ListNode headB) {
        ListNode node1 = headA;
        ListNode node2 = headB;
        while(node1 != null || node2 != null){
            if(node1 == null){
                node1 = headB;
            }
            if(node2 == null){
                node2 = headA;
            }
            if(node1 == node2){
                return node1;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        return null;
    }


























//
//    private ListNode solution(ListNode headA,ListNode headB){
//        ListNode node1 = headA;
//        ListNode node2 = headB;
//        while(headA != null || headB != null){
//            if(headA == null){
//                headA = node2;
//            }
//            if(headB == null){
//                headB = node1;
//            }
//            if(headA == headB){
//                return headA;
//            } else {
//                headA = headA.next;
//                headB = headB.next;
//            }
//        }
//        return null;
//    }

}
